package week02

// 912. 排序数组
// https://leetcode-cn.com/problems/sort-an-array/

func sortArray(nums []int) []int {
	// quickSort(nums)
	// return nums
	return mergeSort(nums)
}

// 归并排序
func mergeSort(nums []int) []int {
	var length = len(nums)
	if length <= 1 {
		return nums
	}
	return merge(mergeSort(nums[:length/2]), mergeSort(nums[length/2:]))
}

func merge(nums1, nums2 []int) []int {
	var ans = make([]int, 0, len(nums1)+len(nums2))
	for len(nums1) > 0 && len(nums2) > 0 {
		if nums1[0] > nums2[0] {
			ans = append(ans, nums2[0])
			nums2 = nums2[1:]
		} else {
			ans = append(ans, nums1[0])
			nums1 = nums1[1:]
		}
	}
	if len(nums1) > 0 {
		ans = append(ans, nums1...)
	}
	if len(nums2) > 0 {
		ans = append(ans, nums2...)
	}
	return ans
}


// 快速排序
func quickSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	povit := povitIndex(nums)
	quickSort(nums[:povit+1])
	quickSort(nums[povit+1:])
}

func povitIndex(nums []int) int {
	var left, right = 0, len(nums)-1
	var povit = right / 2
	var povitVal = nums[povit]
	for left <= right {
		for nums[left] < povitVal {
			left++
		}
		for nums[right] > povitVal {
			right--
		}
		if left == right {
			break
		}
		if left < right {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}
	return right    // right刚好是分割点或偏向左边的点，分组时要分到左边一组
					// 如果返回的是left，分组时要分到右边一组
}
